import java.util.HashSet;

/*
 * @lc app=leetcode.cn id=52 lang=java
 *
 * [52] N皇后 II
 *
 * https://leetcode-cn.com/problems/n-queens-ii/description/
 *
 * algorithms
 * Hard (76.49%)
 * Likes:    88
 * Dislikes: 0
 * Total Accepted:    13.2K
 * Total Submissions: 17.3K
 * Testcase Example:  '4'
 *
 * n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 *
 *
 * 上图为 8 皇后问题的一种解法。
 *
 * 给定一个整数 n，返回 n 皇后不同的解决方案的数量。
 *
 * 示例:
 *
 * 输入: 4
 * 输出: 2
 * 解释: 4 皇后问题存在如下两个不同的解法。
 * [
 * [".Q..",  // 解法 1
 * "...Q",
 * "Q...",
 * "..Q."],
 *
 * ["..Q.",  // 解法 2
 * "Q...",
 * "...Q",
 * ".Q.."]
 * ]
 *
 *
 */

// @lc code=start
class Solution {
    int res;
    boolean[] row;
    boolean[] col;
    Set<Integer> line1;
    Set<Integer> line2;
    public int totalNQueens(int n) {
        this.row = new boolean[n];
        this.col = new boolean[n];
        this.line1 = new HashSet<>();
        this.line2 = new HashSet<>();
        dfs(n, 0);
        return this.res;
    }

    void dfs(int n, int row) {
        if(row == n) {
            this.res ++;
            return;
        }
        for(int col=0; col < n; col++) {
            if(canPut(row, col)) {
                put(row, col);
                dfs(n, row+1);
                unput(row, col);
            }
        }
    }

    boolean canPut(int row, int col) {
        return !this.row[row] && !this.col[col]
                && !this.line1.contains(row+col)
                && !this.line2.contains(row-col);
    }

    void put(int row, int col) {
        this.row[row] = true;
        this.col[col] = true;
        this.line1.add(row+col);
        this.line2.add(row-col);
    }

    void unput(int row, int col) {
        this.row[row] = false;
        this.col[col] = false;
        this.line1.remove(row+col);
        this.line2.remove(row-col);
    }
}
// @lc code=end

